package codingforgreat.lchot150;

import java.util.Arrays;

public class Lc091 {
    public int numDecodings(String s) {
        char[] str = s.toCharArray();
        int[] map = new int[str.length + 1];
        Arrays.fill(map,-1);
        return func(str,0,map);
    }
    public int func(char[] str,int index,int[] map){
        if(map[index] != -1){
            return map[index];
        }
        if(index == str.length){
            return 1;
        }
        if(str[index] == '0'){
            return 0;
        }
        int ways = func(str,index + 1,map);
        if(index + 1 <= str.length - 1){
            int num = (str[index] - '0') * 10 + (str[index + 1] - '0');
            if(num < 27){
                ways += func(str,index + 2,map);
            }
        }
        map[index] = ways;
        return ways;
    }
}
